<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>41. 缺失的第一个正数</title>
  </head>
  <body>
    <script>
      //     给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

      // 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
      //

      // 示例 1：

      // 输入：nums = [1,2,0]
      // 输出：3
      // 示例 2：

      // 输入：nums = [3,4,-1,1]
      // 输出：2
      // 示例 3：

      // 输入：nums = [7,8,9,11,12]
      // 输出：1
      //

      // 提示：

      // 1 <= nums.length <= 5 * 105
      // -231 <= nums[i] <= 231 - 1

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/first-missing-positive
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {number[]} nums
       * @return {number}
       */
      var firstMissingPositive = function (nums) {
        const N = nums.length
        debugger
        for (let i = 0; i < N; i++) {
          if (nums[i] <= 0) nums[i] = N + 1
        }
        for (let i = 0; i < N; i++) {
          let x = Math.abs(nums[i])
          if (x >= 1 && x <= N) {
            nums[x - 1] = nums[x - 1] < 0 ? nums[x - 1] : -nums[x - 1]
          }
        }
        for (let i = 0; i < N; i++) {
          if (nums[i] >= 0) return i + 1
        }
        return N + 1
      }
      console.log(firstMissingPositive([3, 4, -1, 1]))
    </script>
  </body>
</html>
